1. Technical Field
The present invention pertains to wireless networks employing neighbor discovery protocols. In particular, the present invention pertains to multi-hop wireless Ad-Hoc networks employing neighbor discovery with each node being assigned a unique time slot to broadcast neighbor discovery (e.g., HELLO) messages.
2. Discussion of the Related Art
Neighbor discovery is essential in every wireless Ad-Hoc communication network. A network node has to announce its existence before network communications are able to commence. In an Ad-Hoc network, the neighbor topology information is exchanged locally. This allows a node to determine node location and adjacency within the network for routing. The neighbor discovery protocol further tracks a lost or new neighbor to enable a timely update of the internal routing tables. The most commonly used neighbor discovery algorithm is periodic-operation-based. In this approach, a node periodically exchanges neighbor discovery (e.g., HELLO) packets or messages with neighboring nodes. The neighbor discovery message is broadcast in a Carrier Sense Multiple Access (CSMA) protocol, where Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) is a commonly used media access technique for Ad-Hoc wireless networks. The broadcast message includes the neighbors known to the transmitting node (e.g., the nodes from which the transmitting node has received a communication). When a receiving node is present within a neighboring node listing of a received neighbor discovery message, a two-way communication has been established between the receiving and transmitting nodes.
Recently, there have been some attempts to enhance the periodic-operation-based algorithm. For example, a neighbor exchange protocol (NXP) has network nodes send HELLO packets only if no other packets have been sent within a timeout period. Further, multi-hop relaying using a combination of broadcast and unicast has been employed to enhance unidirectional links.
The neighbor discovery protocols discussed above suffer from several disadvantages. In particular, the protocol deficiencies relate to reliability, overhead, update speed and latency for detecting new and lost neighbors. Reliability pertains to the degree of reliability in which neighboring nodes can receive HELLO messages and update speed determines the time in which a missing neighbor can be detected. Update speed relates to the length of the HELLO time interval or period or, in other words, the frequency of HELLO message transmissions. These two parameters are generally conflicting because fast or high frequency transmissions of HELLO packets will increase the traffic load, thereby causing collisions which decrease reliability.
In an Ad-Hoc network, the network nodes compete for a limited number of channels. The CSMA/CA protocol is typically employed to reduce the probability of multiple nodes accessing the channels at the same time. If simultaneous channel access occurs, collisions are unavoidable and HELLO packets are lost. The probability of collisions increases with the rate or frequency of HELLO packet transmissions. If each network node is stationary, the HELLO time interval or period can be long without degrading network performance. However, in a mobile environment (e.g., military battlefield, etc.), nodes move or travel constantly. A node may acquire a new neighbor or lose an existing neighbor. If the nodes move at a fast rate, the frequency of HELLO packets must be increased in order to track the changing neighbors. However, this situation increases the number of collisions and overhead, thereby significantly reducing reliability and diverting bandwidth from user data transmissions. In fact, in a very volatile network, a majority of the bandwidth may be utilized to transmit HELLO packets, thereby compromising the usefulness of the network.
Further, uncertainty exists with respect to detection of a missing, or lost, neighboring node. Generally, several HELLO time intervals or periods are required to expire before a neighbor can be designated as lost. However, if the number of expired HELLO periods is set to an excessive threshold, a lost neighbor cannot be detected in a timely manner. Conversely, valid neighbors may be discarded in response to assigning an insufficient number of HELLO periods as the threshold.
With respect to overhead, the HELLO message transmitted using CSMA/CA requires a reservation. Accordingly, four packets (e.g., Request-to-Send (RTS), Clear-to-Send (CTS), message, and Acknowledgment (ACK)) are transmitted for every data packet transmission, pursuant to conventional standard IEEE802.11. An RTS packet is transmitted from the source node to reserve a channel. A CTS packet is transmitted from the destination node to confirm the reservation, while an ACK packet is transmitted from the destination node to confirm receipt of a data packet. In other words, each HELLO packet is accompanied by three additional overhead packets. In terms of the total number of packets exchanged, the overhead is seventy-five percent (75%).